{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Closest Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nearestPalindromic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找最近的回文数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个表示整数的字符串&nbsp;<code>n</code> ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。</p>\n",
    "\n",
    "<p>“最近的”定义为两个整数<strong>差的绝对值</strong>最小。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = \"123\"\n",
    "<strong>输出:</strong> \"121\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = \"1\"\n",
    "<strong>输出:</strong> \"0\"\n",
    "<strong>解释:</strong> 0 和 2是最近的回文，但我们返回最小的，也就是 0。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n.length &lt;= 18</code></li>\n",
    "\t<li><code>n</code>&nbsp;只由数字组成</li>\n",
    "\t<li><code>n</code>&nbsp;不含前导 0</li>\n",
    "\t<li><code>n</code>&nbsp;代表在&nbsp;<code>[1, 10<sup>18</sup>&nbsp;- 1]</code> 范围内的整数</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-closest-palindrome](https://leetcode.cn/problems/find-the-closest-palindrome/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-closest-palindrome](https://leetcode.cn/problems/find-the-closest-palindrome/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"123\"', '\"1\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        N=len(n)\n",
    "        if N==1:\n",
    "            return str(int(n)-1)\n",
    "        cands = [str(10**power+ shift) for power in (N,N-1) for shift in (1,-1)]\n",
    "        prefix = n[:(N+1)//2]\n",
    "        P = int(prefix)\n",
    "        for cand in map(str,(P-1,P,P+1)):\n",
    "            cand = cand + (cand[:-1] if N%2 else cand)[::-1]\n",
    "            cands.append(cand)      \n",
    "                \n",
    "        ans = \"\"\n",
    "        def delta(cand):\n",
    "            return abs(int(cand) - int(n))\n",
    "        for cand in cands:\n",
    "            if cand != n and not cand.startswith('00'):\n",
    "                if not ans or delta(cand)< delta(ans) or delta(cand)== delta(ans) and int(cand) < int(ans):\n",
    "                    ans = cand\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n):\n",
    "        length, N ,ans = len(n), int(n), 10**9\n",
    "        # 1.将字符串转化为整数\n",
    "        if N < 10 or N == 10 ** (length-1):  # 当给出数字：大于0，小于10 时，直接返回比它小的下一位即可\n",
    "            return str(N-1)\n",
    "        if N - 1 == 10 ** (length-1):  #  当给出数字为首尾皆为1，中间为0时，直接返回该数字-2的值即可\n",
    "            return str(N-2)\n",
    "        if N + 1 == 10 ** length:  # 当给出数字为皆为9时，直接返回该数字+2的值即可\n",
    "            return str(N + 2)\n",
    "\n",
    "        pre = int(n[:(length+1)//2])  # 确认这个数字前面半部分（奇数位取前几位）\n",
    "        print(pre)\n",
    "        tmp = [s[:length//2] + s[::-1] for s in [str(pre + dx) for dx in (-1, 0, 1)]]\n",
    "        # 找出与之对应的回文字符串，用临时列表组装起来\n",
    "        for X in tmp:\n",
    "            if abs(int(X)-N) < ans and abs(int(X)-N) !=0:\n",
    "                ans_1 = X\n",
    "                ans = abs(int(X)-N)\n",
    "        return str(ans_1)\n",
    "        # return min(tmp, key=lambda x: (x==n, abs(int(x)-N)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        candidates = [10 ** (m - 1) - 1, 10 ** m + 1]\n",
    "        selfPrefix = int(n[:(m + 1) // 2])\n",
    "        for x in range(selfPrefix - 1, selfPrefix + 2):\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y:\n",
    "                x = x * 10 + y % 10\n",
    "                y //= 10\n",
    "            candidates.append(x)\n",
    "\n",
    "        ans = -1\n",
    "        selfNumber = int(n)\n",
    "        for candidate in candidates:\n",
    "            if candidate != selfNumber:\n",
    "                if ans == -1 or \\\n",
    "                        abs(candidate - selfNumber) < abs(ans - selfNumber) or \\\n",
    "                        abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:\n",
    "                    ans = candidate\n",
    "        return str(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getPalindromeByHalf(half: Union[str, int], even=True) -> str:\n",
    "    \"\"\"给定回文的一半,返回偶数长度/奇数长度的回文字符串.\"\"\"\n",
    "    if even:\n",
    "        return f\"{half}{str(half)[::-1]}\"\n",
    "    return f\"{half}{str(half)[:-1][::-1]}\"\n",
    "\n",
    "\n",
    "INF = int(1e20)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        def bisect(length: int) -> None:\n",
    "            nonlocal res, minDiff\n",
    "\n",
    "            left = 10 ** ((length - 1) >> 1)\n",
    "            right = left * 10 - 1\n",
    "\n",
    "            while left <= right:\n",
    "                mid = (left + right) >> 1\n",
    "                palindrome = int(getPalindromeByHalf(mid, length % 2 == 0))\n",
    "                diff = abs(palindrome - target)\n",
    "                if palindrome != target:\n",
    "                    if diff < minDiff:\n",
    "                        minDiff = abs(palindrome - target)\n",
    "                        res = palindrome\n",
    "                    elif diff == minDiff and palindrome < res:\n",
    "                        res = palindrome\n",
    "\n",
    "                if palindrome >= target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "\n",
    "        if int(n) <= 9:\n",
    "            return str(int(n) - 1)\n",
    "\n",
    "        target = int(n)\n",
    "        minDiff, res = INF, INF\n",
    "        bisect(len(n))\n",
    "        bisect(len(n) + 1)\n",
    "        bisect(len(n) - 1)\n",
    "\n",
    "        return str(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        candidates = [10 ** (m - 1) - 1, 10 ** m + 1]\n",
    "        selfPrefix = int(n[:(m + 1) // 2])\n",
    "        for x in range(selfPrefix - 1, selfPrefix + 2):\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y:\n",
    "                x = x * 10 + y % 10\n",
    "                y //= 10\n",
    "            candidates.append(x)\n",
    "\n",
    "        ans = -1\n",
    "        selfNumber = int(n)\n",
    "        for candidate in candidates:\n",
    "            if candidate != selfNumber:\n",
    "                if ans == -1 or abs(candidate - selfNumber) < abs(ans - selfNumber) or abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:\n",
    "                    ans = candidate\n",
    "        return str(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        candidates = [10 ** (m - 1) - 1, 10 ** m + 1]\n",
    "        selfPrefix = int(n[:(m + 1) // 2])\n",
    "        for x in range(selfPrefix - 1, selfPrefix + 2):\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y:\n",
    "                x = x * 10 + y % 10\n",
    "                y //= 10\n",
    "            candidates.append(x)\n",
    "\n",
    "        ans = -1\n",
    "        selfNumber = int(n)\n",
    "        for candidate in candidates:\n",
    "            if candidate != selfNumber:\n",
    "                if ans == -1 or \\\n",
    "                        abs(candidate - selfNumber) < abs(ans - selfNumber) or \\\n",
    "                        abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:\n",
    "                    ans = candidate\n",
    "        return str(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, s: str) -> str:\n",
    "        \"\"\"\n",
    "        由于低位变化可能带来高位变化\n",
    "        对于偶数abcd 前两位可能是ab ab+1 ab-1 \n",
    "        因此对于abcde来说最近的回文前三位可能是abc abc+1 和 abc-1 其他位置根据前三位确定\n",
    "        但如果abcde是999xx +1得到的是1000001 但实际100001更好\n",
    "        同理abcde是100xx -1得到的就是999 但实际上9999更优\n",
    "        综上就要考虑五个值 后面两个值是10^(n-1)-1 和10^n+1 n是长度\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        num = int(s)\n",
    "        rsSet = set() #存放结果\n",
    "        rsSet.add(10**(n-1)-1) #加入边界\n",
    "        rsSet.add(10**n+1)\n",
    "        prefix = int(s[:(n+1)//2]) #截取数字前一半\n",
    "        # 找到相邻的回文数\n",
    "        for i in range(prefix-1,prefix+2):\n",
    "            buffer =list(str(i))\n",
    "            startIdx = len(buffer)-1 if n%2==0 else len(buffer)-2 #偶数只有ab因此从b开始处理 而奇数时abc中的b是倒数第二个\n",
    "            while startIdx>=0:\n",
    "                buffer.append(buffer[startIdx])\n",
    "                startIdx -= 1\n",
    "            rsSet.add(int(\"\".join(buffer)))\n",
    "        rs = None\n",
    "        for i in rsSet:\n",
    "            if i==num:\n",
    "                continue\n",
    "            if rs is None or abs(i-num)<abs(rs-num):\n",
    "                rs = i\n",
    "            elif  abs(i-num)==abs(rs-num) and i<rs:\n",
    "                rs = i\n",
    "        return str(rs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        length, int_n = len(n), int(n)\n",
    "        if int_n < 10 or int_n == 10 ** (length-1): return str(int_n-1)\n",
    "        if int_n - 1 == 10 ** (length-1): return str(int_n-2)\n",
    "        if int_n + 1 == 10 ** length: return str(int_n + 2)\n",
    "\n",
    "        pre = int(n[:(length+1)//2])\n",
    "        tmp = [s[:length//2] + s[::-1] for s in [str(pre + dx) for dx in (-1, 0, 1)]]\n",
    "        return min(tmp, key=lambda x: (x==n, abs(int(x)-int_n)))\n",
    "\n",
    "# 作者：洛必达泉\n",
    "# 链接：https://leetcode.cn/problems/find-the-closest-palindrome/solutions/763762/7xing-shuang-bai-by-luo-bi-da-quan-j37e/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        candidates = [10 ** (m - 1) - 1, 10 ** m + 1]\n",
    "        prefix = int(n[:(m+1)//2])\n",
    "        for x in range(prefix-1, prefix+2):\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y:\n",
    "                x = x * 10 + y % 10\n",
    "                y //= 10\n",
    "            candidates.append(x)\n",
    "        \n",
    "        ans = -1\n",
    "        num = int(n)\n",
    "        for cand in candidates:\n",
    "            if cand != num:\n",
    "                if ans == -1 or abs(cand - num) < abs(ans - num) or (abs(cand - num) == abs(ans - num) and cand < ans):\n",
    "                    ans = cand\n",
    "        return str(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        \"\"\"\n",
    "        题目要求：给定整数的字符串n，返回与它最近(差的绝对值最小)的回文整数（不包括自身,若不止一个,返回较小的那个)\n",
    "        :param n: 给定的整数n，以字符串形式给出\n",
    "        :return: 返回距离n最近的回文整数\n",
    "        \"\"\"\n",
    "        # 解题思路：题目本身不难理解，难点在于如何确定最近的那个回文数\n",
    "        # 构造回文数有一个直观的方法：用原数的较高位的数字替换其对应的较低位，此时修改的都是较低位的数字，因此构造出的新的整数与原数较为接近\n",
    "        # 明确了这种构造方法，那么如何找到这些备选数呢，这里采用了一种策略，可以理解为贪心\n",
    "        # 实际上最近的那个数最多也就只有三种情况：\n",
    "        # 用原数的前半部分替换后半部分得到的回文整数；用原数的前半部分加一后的结果替换后半部分得到的回文整数；用原数的前半部分减一后的结果替换后半部分得到的回文整数\n",
    "        # 简言之，记原数的前半部分为a,就是将a、a+1、a-1为左边分别构建一个回文数，然后选择三个数中最近的那个即可(别忘记排除本身的情况)\n",
    "        # 基本思路已经形成了，还需考虑一下细节和特殊情况\n",
    "        # 细节1:在分割前半部分时，若长度为奇数，则多给其分一位(一个小技巧，取前(len+1)//2个，如果原来是奇数，就会多取一个，如果是偶数，则还是刚好取一半)\\\n",
    "        # 细节2：当长度为奇数时，a为左半边会加上中间一位，此时反转拼接时需要少拼接一位\n",
    "        # 特殊情况1: 小于10的个位数时，个位数全部都是回文的，故直接返回n-1即可(n+1的距离一样近，但是要取小的)\n",
    "        # 特殊情况2：n为10的整数幂时，也是直接返回n-1即可，例如：n为100，100-1=99天然回文数\n",
    "        # 特殊情况3：n为11时，这是一个大坑，该方法下需要单独考虑，利用这种构造方法是得不到答案9的\n",
    "        # 特殊情况4(其实可以不用单独列出，一般的构造可以包含，单独列出相当于节省时间呗)：n全为9的时候，直接返回n+2\n",
    "        if int(n) < 10 or int(n[::-1]) == 1:  # 特殊情况1、2。解释一下int(n[::-1])，逆序以后数为1，原数不就是10的整数幂咯(不难理解)\n",
    "            return str(int(n) - 1)\n",
    "        if n == '11':  # 特殊情况3\n",
    "            return '9'\n",
    "        if set(n) == {'9'}:  # 特殊情况4\n",
    "            return str(int(n) + 2)\n",
    "        l = len(n)  # 取长度\n",
    "        a, b = n[:(l + 1) // 2], n[(l + 1) // 2:]  # 分出前半部分和后半部分(用上述小技巧完美解决细节1)\n",
    "        list_a = [str(int(a) - 1), a, str(int(a) + 1)]  # 构造出a、a+1、a-1\n",
    "        res = [aa + aa[len(b) - 1::-1] for aa in list_a]  # 拼接构造出备选数，反转逆序时只取b(后半部分)的长度就行，可以完美解决细节2\n",
    "        # 这个排序的意思是，先按是否等于n排序(等就在后面，相当于大)，在按绝对值大小排序(小的在前)，这样排序后天然排除了本身，因为本身必在最后\n",
    "        return min(res, key=lambda x: (x == n, abs(int(x) - int(n))))  # 最后返回距离最近的那个数(排除自身)\n",
    "        # 不能理解这个排序的话就用下面的朴素方法呗\n",
    "        # if n in res:\n",
    "        #     res.remove(n)\n",
    "        # return min(res, key=lambda x: abs(int(x) - int(n)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        l = len(n)\n",
    "        if l == 1:\n",
    "            return str(int(n) - 1)\n",
    "        s = n[: l // 2 + l % 2] # 截取前半段，如果长度为奇数，则中间的也包括\n",
    "        s1 = str(int(s) - 1)\n",
    "        s2 = str(int(s) + 1)\n",
    "        # min前几个参数是可能的最小值，key是比较这些数和n的距离，如果abs(int(x) - int(n)=0则返回inf,,即把距离设成一个很大的数（inf）用于排除自身；如果两个数距离相等，就直接比较这两个数（int(x)），返回较小的。\n",
    "        # 考虑几个特殊用例，输入100，要输出99不能输出101\n",
    "        # 输入99，要输出101\n",
    "        # 输入88，要输出77\n",
    "        # 输入11011，要输出11111而非10901\n",
    "        # return min(\n",
    "        #     '9' * (l - 1),  # 输入100，要输出99\n",
    "        #     '1' + '0' * (l - 1) + '1', # 输入99，要输出101\n",
    "        #     s + (s[:-1][::-1] if l % 2 else s[::-1]),    # 大多数情况这一条都会符合\n",
    "        #     s1 + (s1[:-1][::-1] if l % 2 else s1[::-1]), # 输入88，要输出77\n",
    "        #     s2 + (s2[:-1][::-1] if l % 2 else s2[::-1]), # 输入11011，要输出11111而非10901\n",
    "        #     key=lambda x: (abs(int(x) - int(n) or inf), int(x)) # \n",
    "        # )\n",
    "        arr = ['9' * (l - 1), \n",
    "            '1' + '0' * (l - 1) + '1',\n",
    "            s + (s[:-1][::-1] if l % 2 else s[::-1]), \n",
    "            s1 + (s1[:-1][::-1] if l % 2 else s1[::-1]),\n",
    "            s2 + (s2[:-1][::-1] if l % 2 else s2[::-1])]\n",
    "        diff = inf\n",
    "        ans = ''\n",
    "        for x in arr:\n",
    "            if abs(int(x) - int(n)) != 0:\n",
    "                if abs(int(x) - int(n)) < diff:\n",
    "                    diff = abs(int(x) - int(n))\n",
    "                    ans = x\n",
    "                elif abs(int(x) - int(n)) == diff and int(x) < int(ans):\n",
    "                    ans = x\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        candidates = [10 ** m + 1, 10 ** (m - 1) - 1]\n",
    "        selfPrefix = int(n[:(m + 1) // 2])\n",
    "        for x in range(selfPrefix - 1, selfPrefix + 2):\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y:\n",
    "                x = x * 10 + y % 10\n",
    "                y //= 10\n",
    "            candidates.append(x)\n",
    "        selfNumber = int(n)\n",
    "        ans = -1\n",
    "        for candidate in candidates:\n",
    "            if candidate != selfNumber:\n",
    "                if abs(candidate - selfNumber) < abs(ans - selfNumber) or \\\n",
    "                abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:\n",
    "                    ans = candidate\n",
    "        return str(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        candidates = [10 ** (m - 1) - 1, 10 ** m + 1]\n",
    "        selfPrefix = int(n[:(m + 1) // 2])\n",
    "        for x in range(selfPrefix - 1, selfPrefix + 2):\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y:\n",
    "                x = x * 10 + y % 10\n",
    "                y //= 10\n",
    "            candidates.append(x)\n",
    "\n",
    "        ans = -1\n",
    "        selfNumber = int(n)\n",
    "        for candidate in candidates:\n",
    "            if candidate != selfNumber:\n",
    "                if ans == -1 or \\\n",
    "                        abs(candidate - selfNumber) < abs(ans - selfNumber) or \\\n",
    "                        abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:\n",
    "                    ans = candidate\n",
    "        return str(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def nearestPalindromic(self, n: str) -> str:\r\n",
    "        m = len(n)\r\n",
    "        candidates = [10 ** (m - 1) - 1, 10 ** m + 1]\r\n",
    "        selfPrefix = int(n[:(m + 1) // 2])\r\n",
    "        for x in range(selfPrefix - 1, selfPrefix + 2):\r\n",
    "            y = x if m % 2 == 0 else x // 10\r\n",
    "            while y:\r\n",
    "                x = x * 10 + y % 10\r\n",
    "                y //= 10\r\n",
    "            candidates.append(x)\r\n",
    "\r\n",
    "        ans = -1\r\n",
    "        selfNumber = int(n)\r\n",
    "        for candidate in candidates:\r\n",
    "            if candidate != selfNumber:\r\n",
    "                if ans == -1 or \\\r\n",
    "                        abs(candidate - selfNumber) < abs(ans - selfNumber) or \\\r\n",
    "                        abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:\r\n",
    "                    ans = candidate\r\n",
    "        return str(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        if len(n) == 1:\n",
    "            return str(int(n) - 1)\n",
    "        l = len(n)\n",
    "        half, v, ov = n[:l//2], int(n[:(l+1)//2]), int(n)\n",
    "        res = set()\n",
    "        s1, s2 = str(v-1), str(v+1)\n",
    "        res.add(\"9\"*(l-1))\n",
    "        res.add(\"1\"+\"0\"*(l-1)+\"1\")\n",
    "\n",
    "        if l%2:\n",
    "            res.add(s1[:-1] + s1[-1] + s1[:-1][::-1])\n",
    "            res.add(s2[:-1] + s2[-1] + s2[:-1][::-1])\n",
    "        else:\n",
    "            res.add(s1 + s1[::-1])\n",
    "            res.add(s2 + s2[::-1])\n",
    "        if n[::-1] != n:\n",
    "            res.add(half + n[l//2] + half[::-1] if l%2 else half + half[::-1])\n",
    "        if n in res:\n",
    "            res.remove(n)\n",
    "\n",
    "        return min(res, key = lambda x: (abs((k:=int(x))-ov),k))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        candidates = [10 ** (m - 1) - 1, 10 ** m + 1]\n",
    "        selfPrefix = int(n[:(m + 1) // 2])\n",
    "        for x in range(selfPrefix - 1, selfPrefix + 2):\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y:\n",
    "                x = x * 10 + y % 10\n",
    "                y //= 10\n",
    "            candidates.append(x)\n",
    "\n",
    "        ans = -1\n",
    "        selfNumber = int(n)\n",
    "        for candidate in candidates:\n",
    "            if candidate != selfNumber:\n",
    "                if ans == -1 or \\\n",
    "                        abs(candidate - selfNumber) < abs(ans - selfNumber) or \\\n",
    "                        abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:\n",
    "                    ans = candidate\n",
    "        return str(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        siz = len(n)\n",
    "        if siz==1:\n",
    "            return str(int(n)-1)\n",
    "        \n",
    "        if n==(\"9\"*siz):\n",
    "            return \"1\"+\"0\"*(siz-1)+\"1\"\n",
    "        \n",
    "        \n",
    "\n",
    "        half = siz//2\n",
    "        first = n[:half]\n",
    "        ans = []\n",
    "        if siz%2==1:\n",
    "            mid = int(n[half])\n",
    "            mids = [mid, mid+1, mid-1]\n",
    "            mids = [m for m in mids if 0<=m<=9]\n",
    "\n",
    "            ans = [first+str(m)+first[::-1] for m in mids]\n",
    "            ans = [int(k) for k in ans if k!=n]\n",
    "        else:\n",
    "            f = int(first)\n",
    "            fs = [str(f), str(f+1), str(f-1)]\n",
    "            fs = [f for f in fs if len(f)==len(first) and int(f)!=0]\n",
    "            \n",
    "            ans = [f+f[::-1] for f in fs]\n",
    "            ans = [int(k) for k in ans if k!=n]\n",
    "        \n",
    "        ans.append(int(\"9\"*(siz-1)))\n",
    "        ans.sort()\n",
    "\n",
    "        print(ans)\n",
    "        res = ans[0]\n",
    "        dif = abs(int(ans[0])-int(n))\n",
    "\n",
    "        # 找最接近的\n",
    "        for k in ans[1:]:\n",
    "            if abs(int(k)-int(n))<dif:\n",
    "                dif = abs(int(k)-int(n))\n",
    "                res = k\n",
    "        return str(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        length, int_n = len(n), int(n)\n",
    "        if int_n < 10 or int_n == 10 ** (length-1): return str(int_n-1)\n",
    "        if int_n - 1 == 10 ** (length-1): return str(int_n-2)\n",
    "        if int_n + 1 == 10 ** length: return str(int_n+2)\n",
    "\n",
    "        pre = int(n[:(length+1)//2])\n",
    "        tmp = [s[:length//2] + s[::-1] for s in [str(pre+dx) for dx in (-1, 0, 1)]]\n",
    "        return min(tmp, key=lambda x: (x==n, abs(int(x)-int_n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        l = len(n)\n",
    "        nn = int(n)\n",
    "        candidates = [10 ** (l - 1) - 1, 10 ** l + 1]\n",
    "        part = n[:(l + 1) // 2]\n",
    "        npart = int(part)\n",
    "        for p in range(npart - 1, npart + 2):\n",
    "            num = p\n",
    "            right = p if l % 2 == 0 else p // 10\n",
    "            while right > 0:\n",
    "                num = num * 10 + right % 10\n",
    "                right //= 10\n",
    "            candidates.append(num)\n",
    "\n",
    "        answer = None\n",
    "        min_diff = int(n)\n",
    "        for c in candidates:\n",
    "            if c == nn:\n",
    "                continue\n",
    "            diff = abs(nn - c)\n",
    "            if answer is None or diff < min_diff or (diff == min_diff and c < answer):\n",
    "                answer = c\n",
    "                min_diff = diff\n",
    "\n",
    "        return str(answer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "\n",
    "        candidates = [10 ** (m-1)-1, 10 ** m + 1]\n",
    "\n",
    "        prefix = int(n[:(m+1)//2])\n",
    "\n",
    "        for x in range(prefix-1, prefix+2):\n",
    "            y = x\n",
    "            if m % 2 != 0:\n",
    "                y = x // 10\n",
    "\n",
    "            while y:\n",
    "                x = x * 10 + y % 10\n",
    "                y = y // 10\n",
    "            candidates.append(x)\n",
    "\n",
    "        res = -1\n",
    "        orig_n = int(n)\n",
    "        for candidate in candidates:\n",
    "            if candidate != orig_n:\n",
    "                if abs(candidate-orig_n) < abs(res-orig_n) or (abs(candidate-orig_n) == abs(res-orig_n) and candidate < res):\n",
    "                    res = candidate\n",
    "\n",
    "        return str(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        length, int_n = len(n), int(n)\n",
    "        if int_n < 10 or int_n == 10 ** (length-1): return str(int_n-1)\n",
    "        if int_n - 1 == 10 ** (length-1): return str(int_n-2)\n",
    "        if int_n + 1 == 10 ** length: return str(int_n + 2)\n",
    "\n",
    "        pre = int(n[:(length+1)//2])\n",
    "        tmp = [s[:length//2] + s[::-1] for s in [str(pre + dx) for dx in (-1, 0, 1)]]\n",
    "        return min(tmp, key=lambda x: (x==n, abs(int(x)-int_n)))\n",
    "\n",
    "# 作者：洛必达泉\n",
    "# 链接：https://leetcode.cn/problems/find-the-closest-palindrome/solutions/763762/7xing-shuang-bai-by-luo-bi-da-quan-j37e/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m, l = len(n), int(n)\n",
    "\n",
    "        # 0-9 和 10^n 次幂的全部按照 n-1 获得回文串\n",
    "        if l < 10 or l == 10 ** (m-1):\n",
    "            return str(l-1)\n",
    "\n",
    "        # 10^n - 1 次幂的全部按照 n+2 获得回文串\n",
    "        if l == 10 ** m - 1: \n",
    "            return str(l + 2)\n",
    "\n",
    "        # 10^(n-1) + 1 次幂的全部按照 n-2 获得回文串\n",
    "        if l == 10 ** (m-1) + 1: \n",
    "            return str(l-2)\n",
    "\n",
    "        # 其他数据用折半法获取回文字符串\n",
    "        min_num = float('+inf')\n",
    "        palid_num_str = '0'\n",
    "        pre_int = int(n[:(m+1)//2]) # 加一折半，避免分奇偶数\n",
    "\n",
    "        # 最近的回文只可能为前缀整数的±1\n",
    "        for dx in (-1, 0, 1):\n",
    "            palid_pre = str(pre_int + dx)\n",
    "            palid_num = int(palid_pre[:m//2] + palid_pre[::-1])\n",
    "\n",
    "            diff = abs(palid_num - l)\n",
    "            if diff > 0 and min_num > diff:\n",
    "                palid_num_str = str(palid_num)\n",
    "                min_num = diff\n",
    "        return palid_num_str\n",
    "\n",
    "# 作者：int_64\n",
    "# 链接：https://leetcode.cn/problems/find-the-closest-palindrome/solutions/1305585/si-lu-jian-dan-xing-neng-gao-xiao-jie-ji-0h2r/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        candidates = [10 ** (m - 1) - 1, 10 ** m + 1]\n",
    "        selfPrefix = int(n[:(m + 1) // 2])\n",
    "        for x in range(selfPrefix - 1, selfPrefix + 2):\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y:\n",
    "                x = x * 10 + y % 10\n",
    "                y //= 10\n",
    "            candidates.append(x)\n",
    "\n",
    "        ans = -1\n",
    "        selfNumber = int(n)\n",
    "        for candidate in candidates:\n",
    "            if candidate != selfNumber:\n",
    "                if ans == -1 or \\\n",
    "                        abs(candidate - selfNumber) < abs(ans - selfNumber) or \\\n",
    "                        abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:\n",
    "                    ans = candidate\n",
    "        return str(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        candidates = [10 ** (m - 1) - 1, 10 ** m + 1]\n",
    "        selfPrefix = int(n[:(m + 1) // 2])\n",
    "        for x in range(selfPrefix - 1, selfPrefix + 2):\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y:\n",
    "                x = x * 10 + y % 10\n",
    "                y //= 10\n",
    "            candidates.append(x)\n",
    "\n",
    "        ans = -1\n",
    "        selfNumber = int(n)\n",
    "        for candidate in candidates:\n",
    "            if candidate != selfNumber:\n",
    "                if ans == -1 or \\\n",
    "                        abs(candidate - selfNumber) < abs(ans - selfNumber) or \\\n",
    "                        abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:\n",
    "                    ans = candidate\n",
    "        return str(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        # 12345\n",
    "        # 1.前面的一半放在后面 12321\n",
    "        # 2.前面的一半+1放在后面 12421\n",
    "        # 3.前面的一半-1放在后面 12221\n",
    "        # 4.上边界 100001\n",
    "        # 5.下边界 9999\n",
    "        l = len(n)\n",
    "        s = n[:l//2+l%2]\n",
    "        s1 = str(int(s)-1)\n",
    "        s2 = str(int(s)+1)\n",
    "        axis = (-1 if l%2==1 else len(s))\n",
    "        candidate = []\n",
    "        candidate.append(s+s[:axis][::-1])\n",
    "        candidate.append(s1+s1[:axis][::-1])\n",
    "        candidate.append(s2+s2[:axis][::-1])\n",
    "        candidate.append('1'+'0'*(l-1)+'1')\n",
    "        if l-1>0:\n",
    "            candidate.append('9'*(l-1))\n",
    "        # print(candidate)\n",
    "        ans,gap=float('inf'),float('inf')\n",
    "        for num in candidate:\n",
    "            # print(num)\n",
    "            if abs(int(n)-int(num))==0:\n",
    "                continue\n",
    "            tmp = abs(int(n)-int(num))\n",
    "            if tmp<gap:\n",
    "                ans,gap = num,tmp\n",
    "            elif tmp==gap and int(num)<int(ans):\n",
    "                ans = num \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m=len(n)\n",
    "        candidtaes=[10**(m-1)-1,10**(m)+1]\n",
    "        pos=int(n[:(m+1)//2])\n",
    "        for x in range(pos-1,pos+2):\n",
    "            y=x if m%2==0 else x//10\n",
    "            while y:\n",
    "                x=x*10+y%10\n",
    "                y=y//10\n",
    "            candidtaes.append(x)\n",
    "        ans=-1\n",
    "        selfnumber=int(n)\n",
    "        for i in candidtaes:\n",
    "            if i!=selfnumber:\n",
    "                if ans==-1 or abs(i-selfnumber)<abs(ans-selfnumber)or ( abs(i-selfnumber)==abs(ans-selfnumber) and i<ans):\n",
    "                    ans=i\n",
    "        return str(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        length, int_n = len(n), int(n)\n",
    "        if int_n < 10 or int_n == 10 ** (length-1): return str(int_n-1)\n",
    "        if int_n - 1 == 10 ** (length-1): return str(int_n-2)\n",
    "        if int_n + 1 == 10 ** length: return str(int_n + 2)\n",
    "\n",
    "        pre = int(n[:(length+1)//2])\n",
    "        tmp = [s[:length//2] + s[::-1] for s in [str(pre + dx) for dx in (-1, 0, 1)]]\n",
    "        return min(tmp, key=lambda x: (x==n, abs(int(x)-int_n)))\n",
    "\n",
    "# 作者：洛必达泉\n",
    "# 链接：https://leetcode.cn/problems/find-the-closest-palindrome/solutions/763762/7xing-shuang-bai-by-luo-bi-da-quan-j37e/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m, l = len(n), int(n)\n",
    "\n",
    "        # 0-9 和 10^n 次幂的全部按照 n-1 获得回文串\n",
    "        if l < 10 or l == 10 ** (m-1):\n",
    "            return str(l-1)\n",
    "\n",
    "        # 10^n - 1 次幂的全部按照 n+2 获得回文串\n",
    "        if l == 10 ** m - 1: \n",
    "            return str(l + 2)\n",
    "\n",
    "        # 10^(n-1) + 1 次幂的全部按照 n-2 获得回文串\n",
    "        if l == 10 ** (m-1) + 1: \n",
    "            return str(l-2)\n",
    "\n",
    "        # 其他数据用折半法获取回文字符串\n",
    "        min_num = float('+inf')\n",
    "        palid_num_str = '0'\n",
    "        pre_int = int(n[:(m+1)//2]) # 加一折半，避免分奇偶数\n",
    "\n",
    "        # 最近的回文只可能为前缀整数的±1\n",
    "        for dx in (-1, 0, 1):\n",
    "            palid_pre = str(pre_int + dx)\n",
    "            palid_num = int(palid_pre[:m//2] + palid_pre[::-1])\n",
    "\n",
    "            diff = abs(palid_num - l)\n",
    "            if diff > 0 and min_num > diff:\n",
    "                palid_num_str = str(palid_num)\n",
    "                min_num = diff\n",
    "        return palid_num_str\n",
    "\n",
    "# 作者：int_64\n",
    "# 链接：https://leetcode.cn/problems/find-the-closest-palindrome/solutions/1305585/si-lu-jian-dan-xing-neng-gao-xiao-jie-ji-0h2r/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        if m == 1:\n",
    "            return str(int(n) - 1)\n",
    "        # 数位变化导致的回文数字\n",
    "        tmp = [10 ** m + 1, 10 ** (m - 1) - 1]\n",
    "        prefix = int(n[:(m + 1)//2])\n",
    "        for x in [prefix - 1, prefix, prefix + 1]:\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y > 0:\n",
    "                x = x * 10 + y % 10\n",
    "                y //= 10\n",
    "            tmp.append(x)\n",
    "        ans = tmp[0]\n",
    "        print(tmp)\n",
    "        for y in tmp:\n",
    "            if y == int(n) or y == tmp[0]:\n",
    "                continue\n",
    "            if abs(ans - int(n)) > abs(y - int(n)):\n",
    "                ans = y\n",
    "            elif abs(ans - int(n)) == abs(y - int(n)):\n",
    "                ans = min(ans, y)\n",
    "        return str(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m=len(n)\n",
    "        can = [10 ** (m-1)-1,(10**m)+1]\n",
    "        pre=int(n[:(m+1)//2])\n",
    "        for x in range(pre-1,pre+2):\n",
    "            y=x if m%2==0 else (x // 10)\n",
    "            if y:\n",
    "                x=int(str(x)+(str(y)[::-1]))\n",
    "            can.append(x)\n",
    "        ans=-1\n",
    "        n=int(n)\n",
    "        for _can in can:\n",
    "            if _can!=n:\n",
    "                if ans==-1 or abs(_can-n)<abs(ans-n) or (abs(_can-n)==abs(ans-n) and _can<ans):\n",
    "                    ans=_can\n",
    "        return str(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        \"\"\"\n",
    "        题目要求：给定整数的字符串n，返回与它最近(差的绝对值最小)的回文整数（不包括自身,若不止一个,返回较小的那个)\n",
    "        :param n: 给定的整数n，以字符串形式给出\n",
    "        :return: 返回距离n最近的回文整数\n",
    "        \"\"\"\n",
    "        # 解题思路：题目本身不难理解，难点在于如何确定最近的那个回文数\n",
    "        # 构造回文数有一个直观的方法：用原数的较高位的数字替换其对应的较低位，此时修改的都是较低位的数字，因此构造出的新的整数与原数较为接近\n",
    "        # 明确了这种构造方法，那么如何找到这些备选数呢，这里采用了一种策略，可以理解为贪心\n",
    "        # 实际上最近的那个数最多也就只有三种情况：\n",
    "        # 用原数的前半部分替换后半部分得到的回文整数；用原数的前半部分加一后的结果替换后半部分得到的回文整数；用原数的前半部分减一后的结果替换后半部分得到的回文整数\n",
    "        # 简言之，记原数的前半部分为a,就是将a、a+1、a-1为左边分别构建一个回文数，然后选择三个数中最近的那个即可(别忘记排除本身的情况)\n",
    "        # 基本思路已经形成了，还需考虑一下细节和特殊情况\n",
    "        # 细节1:在分割前半部分时，若长度为奇数，则多给其分一位(一个小技巧，取前(len+1)//2个，如果原来是奇数，就会多取一个，如果是偶数，则还是刚好取一半)\\\n",
    "        # 细节2：当长度为奇数时，a为左半边会加上中间一位，此时反转拼接时需要少拼接一位\n",
    "        # 特殊情况1: 小于10的个位数时，个位数全部都是回文的，故直接返回n-1即可(n+1的距离一样近，但是要取小的)\n",
    "        # 特殊情况2：n为10的整数幂时，也是直接返回n-1即可，例如：n为100，100-1=99天然回文数\n",
    "        # 特殊情况3：n为11时，这是一个大坑，该方法下需要单独考虑，利用这种构造方法是得不到答案9的\n",
    "        # 特殊情况4(其实可以不用单独列出，一般的构造可以包含，单独列出相当于节省时间呗)：n全为9的时候，直接返回n+2\n",
    "        if int(n) < 10 or int(n[::-1]) == 1:  # 特殊情况1、2。解释一下int(n[::-1])，逆序以后数为1，原数不就是10的整数幂咯(不难理解)\n",
    "            return str(int(n) - 1)\n",
    "        if n == '11':  # 特殊情况3\n",
    "            return '9'\n",
    "        if set(n) == {'9'}:  # 特殊情况4\n",
    "            return str(int(n) + 2)\n",
    "        l = len(n)  # 取长度\n",
    "        a, b = n[:(l + 1) // 2], n[(l + 1) // 2:]  # 分出前半部分和后半部分(用上述小技巧完美解决细节1)\n",
    "        list_a = [str(int(a) - 1), a, str(int(a) + 1)]  # 构造出a、a+1、a-1\n",
    "        res = [aa + aa[len(b) - 1::-1] for aa in list_a]  # 拼接构造出备选数，反转逆序时只取b(后半部分)的长度就行，可以完美解决细节2\n",
    "        # 这个排序的意思是，先按是否等于n排序(等就在后面，相当于大)，在按绝对值大小排序(小的在前)，这样排序后天然排除了本身，因为本身必在最后\n",
    "        return min(res, key=lambda x: (x == n, abs(int(x) - int(n))))  # 最后返回距离最近的那个数(排除自身)\n",
    "        # 不能理解这个排序的话就用下面的朴素方法呗\n",
    "        # if n in res:\n",
    "        #     res.remove(n)\n",
    "        # return min(res, key=lambda x: abs(int(x) - int(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        candidates = [10 ** (m - 1) - 1, 10 ** m + 1]\n",
    "        selfPrefix = int(n[:(m + 1) // 2])\n",
    "        for x in range(selfPrefix - 1, selfPrefix + 2):\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y:\n",
    "                x = x * 10 + y % 10\n",
    "                y //= 10\n",
    "            candidates.append(x)\n",
    "\n",
    "        ans = -1\n",
    "        selfNumber = int(n)\n",
    "        for candidate in candidates:\n",
    "            if candidate != selfNumber:\n",
    "                if ans == -1 or \\\n",
    "                        abs(candidate - selfNumber) < abs(ans - selfNumber) or \\\n",
    "                        abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:\n",
    "                    ans = candidate\n",
    "        return str(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        if len(n) == 1:\n",
    "            return str(int(n) - 1)\n",
    "        l = len(n)\n",
    "        half, v, ov = n[:l//2], int(n[:(l+1)//2]), int(n)\n",
    "        res = set()\n",
    "        s1, s2 = str(v-1), str(v + 1)\n",
    "        res.add(\"9\" * (l - 1))\n",
    "        res.add(\"1\" + \"0\" * (l - 1) + \"1\")\n",
    "        if l % 2:\n",
    "            res.add(s1[:-1] + s1[-1] + s1[:-1][::-1])\n",
    "            res.add(s2[:-1] + s2[-1] + s2[:-1][::-1])\n",
    "        else:\n",
    "            res.add(s1 + s1[::-1])\n",
    "            res.add(s2 + s2[::-1])\n",
    "        if n[::-1] != n:\n",
    "            res.add(half + n[l//2] + half[::-1] if l % 2 else half + half[::-1])\n",
    "        if n in res:\n",
    "            res.remove(n)\n",
    "        return min(res, key = lambda x:(abs((k:=int(x)) - ov), k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        l=len(n)\n",
    "        if l==1:\n",
    "            return str(int(n)-1)\n",
    "        s=n[:l//2+l%2]\n",
    "        s1=str(int(s)+1)\n",
    "        s2=str(int(s)-1)\n",
    "        return min(\n",
    "            \"9\"*(l-1),\n",
    "            \"1\"+\"0\"*(l-1)+\"1\",\n",
    "            s+s[-1-l%2::-1],\n",
    "            s1+s1[-1-l%2::-1],\n",
    "            s2+s2[-1-l%2::-1],\n",
    "            key=lambda x:(abs(int(x)-int(n))or 1145141919810, int(x))\n",
    "        )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        def getPalindFromLhs(lhs: str, isOdd: bool) -> str:\n",
    "            if lhs == '0' and not isOdd:\n",
    "                return '9'\n",
    "            if isOdd:\n",
    "                return lhs + (lhs[len(lhs)-2::-1] if len(lhs) >= 2 else \"\")\n",
    "            return lhs + lhs[::-1]\n",
    "        if len(n) > 1 and all(c == '9' for c in n):\n",
    "            return str(int(n) + 2)\n",
    "        mid = len(n) // 2\n",
    "        lhs = n[:mid] if len(n) % 2 == 0 else n[:mid + 1]\n",
    "        isOdd = len(n) % 2 == 1\n",
    "        palind = getPalindFromLhs(lhs, isOdd)\n",
    "        lo_lhs = str(int(lhs) - 1)\n",
    "        lo_palind = getPalindFromLhs(lo_lhs, isOdd) if len(lo_lhs) == len(lhs) else '9' * (len(palind) - 1)\n",
    "        hi_lhs = str(int(lhs) + 1)\n",
    "        hi_palind = getPalindFromLhs(hi_lhs, isOdd) if len(hi_lhs) == len(lhs) else '1' + '0' * (len(palind) - 1) + '1'\n",
    "        print(hi_palind, lo_palind, palind, n)\n",
    "        if n < palind:\n",
    "            return lo_palind if int(n) - int(lo_palind) <= int(palind) - int(n) else palind\n",
    "        elif n > palind:\n",
    "            return palind if int(n) - int(palind) <= int(hi_palind) - int(n) else hi_palind\n",
    "        return lo_palind if int(n) - int(lo_palind) <= int(hi_palind) - int(n) else hi_palind"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        candidates = [10**(m-1)-1, 10**m+1]\n",
    "        self_prefix= int(n[:(m+1) // 2])\n",
    "        for x in range(self_prefix-1, self_prefix+2):\n",
    "            y=x if m%2==0 else x//10\n",
    "            while y:\n",
    "                x = x*10 + y % 10\n",
    "                y //= 10\n",
    "            candidates.append(x)\n",
    "        \n",
    "        ans = -1\n",
    "        self_num = int(n)\n",
    "        for candidate in candidates:\n",
    "            if candidate==self_num:\n",
    "                continue\n",
    "            if ans==-1 or \\\n",
    "                abs(candidate-self_num) < abs(ans-self_num) or \\\n",
    "                abs(candidate-self_num)==abs(ans-self_num) and candidate<ans:\n",
    "                ans = candidate\n",
    "        return str(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        # 99, 1001\n",
    "        candidates = [10 ** (m - 1) - 1, 10 ** m + 1]\n",
    "        # 12\n",
    "        selfPrefix = int(n[:(m + 1) // 2])\n",
    "        # 11, 12, 13\n",
    "        # 111, 121, 131\n",
    "        for x in range(selfPrefix - 1, selfPrefix + 2):\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y:\n",
    "                # ! important\n",
    "                x = x * 10 + y % 10\n",
    "                y //= 10\n",
    "            candidates.append(x)\n",
    "\n",
    "        ans = -1\n",
    "        selfNumber = int(n)\n",
    "        for candidate in candidates:\n",
    "            if candidate != selfNumber:\n",
    "                if ans == -1 or abs(candidate - selfNumber) < abs(ans - selfNumber) or abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:\n",
    "                    ans = candidate\n",
    "        return str(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        candidates = [10 ** m + 1, 10 ** (m - 1) - 1]\n",
    "        prefix = int(n[: (m + 1) // 2])\n",
    "        for x in range(prefix - 1, prefix + 2):\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y > 0:\n",
    "                x = 10 * x + y % 10\n",
    "                y //= 10\n",
    "            candidates.append(x)\n",
    "        ans = -1\n",
    "        num = int(n)\n",
    "        for candidate in candidates:\n",
    "            if candidate == num:\n",
    "                continue\n",
    "            if ans == -1 or \\\n",
    "                    abs(candidate - num) < abs(ans - num) or \\\n",
    "                    abs(candidate - num) == abs(ans - num) and candidate < ans:\n",
    "                ans = candidate\n",
    "        return str(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        m = len(n)\n",
    "        # if m == 1:\n",
    "        #     return str(int(n) - 1)\n",
    "        # 数位变化导致的回文数字\n",
    "        tmp = [10 ** m + 1, 10 ** (m - 1) - 1]\n",
    "        prefix = int(n[:(m + 1)//2])\n",
    "        for x in [prefix - 1, prefix, prefix + 1]:\n",
    "            y = x if m % 2 == 0 else x // 10\n",
    "            while y > 0:\n",
    "                x = x * 10 + y % 10\n",
    "                y //= 10\n",
    "            tmp.append(x)\n",
    "        ans = tmp[0]\n",
    "        print(tmp)\n",
    "        for y in tmp:\n",
    "            if y == int(n) or y == tmp[0]:\n",
    "                continue\n",
    "            if abs(ans - int(n)) > abs(y - int(n)):\n",
    "                ans = y\n",
    "            elif abs(ans - int(n)) == abs(y - int(n)):\n",
    "                ans = min(ans, y)\n",
    "        return str(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, num: str) -> str:\n",
    "        n = len(num)\n",
    "        if int(num) < 10:\n",
    "            return str(int(num) - 1)\n",
    "        elif num == '11':\n",
    "            return '9'\n",
    "        elif set(num) == {'9'}:\n",
    "            return str(int(num) + 2)\n",
    "        elif int(num[::-1]) == 1:\n",
    "            return str(int(num) - 1)\n",
    "        left = num[ : n // 2 + n % 2]\n",
    "        res = ''\n",
    "        for cand in (str(int(left) - 1), left, str(int(left) + 1)):\n",
    "            new = cand + cand[ : n // 2][::-1]\n",
    "            if new == num:\n",
    "                continue   \n",
    "            if not res or abs(int(res) - int(num)) > abs(int(new) - int(num)):\n",
    "                res = new \n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestPalindromic(self, n: str) -> str:\n",
    "        length = len(n)\n",
    "        num = int(n)\n",
    "        candidates = set()\n",
    "\n",
    "        # 添加长度加一和减一的情况\n",
    "        candidates.add(10 ** (length - 1) - 1)\n",
    "        candidates.add(10 ** length + 1)\n",
    "\n",
    "        # 获取n的前半部分\n",
    "        prefix = int(n[:(length + 1) // 2])\n",
    "\n",
    "        # 生成所有可能的回文数, 例如：12345 -> 12221, 12321, 12421\n",
    "        for i in range(prefix - 1, prefix + 2):\n",
    "            if length % 2 == 0:\n",
    "                candidate = str(i) + str(i)[::-1]\n",
    "            else:\n",
    "                candidate = str(i) + str(i)[:-1][::-1]\n",
    "            candidates.add(int(candidate))\n",
    "\n",
    "        # 移除原始数字自身\n",
    "        candidates.discard(num)\n",
    "\n",
    "        # 找出与原始数字最接近的回文数\n",
    "        nearest = None\n",
    "        min_diff = float('inf')\n",
    "        for candidate in candidates:\n",
    "            diff = abs(num - candidate)\n",
    "            if diff < min_diff or (diff == min_diff and candidate < nearest):\n",
    "                min_diff = diff\n",
    "                nearest = candidate\n",
    "\n",
    "        return str(nearest)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
